//    Copyright 2009-2011 Ateeq Sharfuddin, Xiaofan Feng.
//    This file is part of Project Viatei.
//
//    Project Viatei is free software: you can redistribute it and/or modify
//    it under the terms of the GNU Lesser General Public License as published by
//    the Free Software Foundation, either version 3 of the License, or
//    (at your option) any later version.
//
//    Project Viatei is distributed in the hope that it will be useful,
//    but WITHOUT ANY WARRANTY; without even the implied warranty of
//    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//    GNU Lesser General Public License for more details.
//
//    You should have received a copy of the GNU Lesser General Public License
//    along with Project Viatei.  If not, see <http://www.gnu.org/licenses/>.

#include "fasthorspool.h"
#include <vector>

#include "delta1.h"

namespace boyermoore
{

	namespace horspool
	{
		namespace machineword
		{
			const unsigned int BYTES_IN_WORD = 8;

			word_t masks[] =
			{
				0x0000000000000000,
				0x00000000000000ff,
				0x000000000000ffff,
				0x0000000000ffffff,
				0x00000000ffffffff,
				0x000000ffffffffff,
				0x0000ffffffffffff,
				0x00ffffffffffffff,
				0xffffffffffffffff
			 };
		}
	}
}


std::list<std::string::size_type> boyermoore::horspool::machineword::find(const std::string & pattern, const std::string & inText)
{
	const char * pat = pattern.c_str();
	const char * txt = inText.c_str();
		
	wordi_t n = inText.length();
	wordi_t m = pattern.length();
		
	// since last three decimal digits determine if divisible by 8....
	const wordi_t mmodWord = m % BYTES_IN_WORD;

	const std::vector<wordi_t> d1 = boyermoore::delta1(pattern);
	std::list<std::string::size_type> offsets;

	
	if (mmodWord != 0)
	{
		word_t mask = 0;
		word_t remainder = 0;

		//memset(&mask, 0xff, mmodWord);
		mask = masks[mmodWord];

		// copy the first few bytes of pattern which are the remainder...
		memcpy(&remainder, pattern.c_str(), mmodWord);

		for (wordi_t j = 0; j <= n - m; j += d1[ txt [ j + m - 1 ] ] )
		{
			wordi_t i;
			for (i = m - BYTES_IN_WORD; i >= 0 && 
				 *(word_t*)(pat + i) == *(word_t*)(txt + i + j); i -= BYTES_IN_WORD );

			// ponder about this more...
			if (i < BYTES_IN_WORD && (*(word_t*)(txt + j) & mask) == remainder)
					offsets.push_back(j);
		}
	}
	else // this block is just an optimization... when pattern length is divisible by word size
	{
		for (wordi_t j = 0; j <= n - m; j += d1[txt[j + m-1]])
		{
			wordi_t i;

			for (i = m - BYTES_IN_WORD; i >= 0 &&
				*(word_t*)(pat + i) == *(word_t*)(txt + i + j); i -= BYTES_IN_WORD );

			if (i < 0)
				offsets.push_back(j);
		}
	}

	return offsets;
		
}